// m

const { ListNode, LinkedList } = require("../../1. 链表基础/1. 建立线性链表")

// 给定两个非空链表的头节点l1和l2来代表两个非负整数，数字最高位位于链表开始位置，每个节点只存储一位数字，除了数字0外，这个两个链表代表的数字都不会以0开头
// 要求将这两个数相加后返回一个新的链表

// 思路： 为了将链表逆序，从而从低位开始处理，我们可以借用两个栈，将链表中所有数字分别压入两个栈中，再依次取出相加

function addTwoNumbers(l1, l2) {
    let stack1 = []
    let stack2 = []
    while (l1) {
        stack1.push(l1.val)
        l1 = l1.next
    }
    while (l2) {
        stack2.push(l2.val)
        l2 = l2.next 
    }
    let res = null
    let carry = 0
    while (stack1.length || stack2.length || carry) {
        let num1 = stack1.length ? stack1.pop() : 0
        let num2 = stack2.length ? stack2.pop() : 0
        let cur_sum = num1 + num2 + carry
        carry = Math.floor(cur_sum / 10)
        cur_sum %= 10
        let cur_node = new ListNode(cur_sum)
        cur_node.next = res
        res = cur_node
    }
    return res
}

let l1 = new LinkedList([7,2,4,3]).head
let l2 = new LinkedList([5,6,4]).head
let result = addTwoNumbers(l1, l2)
console.log(result)